import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    public StringBuffer path;
    public List<String> ret;

    public List<String> letterCasePermutation(String s) {
        path = new StringBuffer();
        ret = new ArrayList<>();

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int pos) {
        if(pos == s.length()) {
            ret.add(path.toString());
            return;
        }

        char ch = s.charAt(pos);
        // 不改变
        path.append(ch);
        dfs(s,pos + 1);
        // 恢复现场
        path.deleteCharAt(path.length() - 1);

        // 改变
        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path.append(tmp);
            dfs(s,pos + 1);
            // 恢复现场
            path.deleteCharAt(path.length() - 1);
        }
    }

    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') {
            return ch -= 32;
        }else {
            return ch += 32;
        }
    }
}